def line_intersection(p1, v1, p2, v2, eps=1e-8):
    """计算两条直线的交点"""
    det = v1[0] * v2[1] - v1[1] * v2[0]
    if abs(det) < eps:
        return None
    dx = p2[0] - p1[0]
    dy = p2[1] - p1[1]
    t = (dx * v2[1] - dy * v2[0]) / det
    return (p1[0] + t * v1[0], p1[1] + t * v1[1])


def find_MN(end_x, end_y, next_x, next_y, next_next_x, next_next_y, R, eps=1e-8):
    A = [end_x,end_y]
    B = [next_x,next_y]
    C = [next_next_x,next_next_y]

    # 计算向量AB和BC
    v1 = (B[0] - A[0], B[1] - A[1])
    v2 = (C[0] - B[0], C[1] - B[1])

    # 计算向量长度
    len1 = (v1[0] ** 2 + v1[1] ** 2) ** 0.5
    len2 = (v2[0] ** 2 + v2[1] ** 2) ** 0.5

    # 处理退化情况（线段长度接近0）
    if len1 < eps or len2 < eps:
        return None, None

    # 计算叉积判断是否平行
    cross = v1[0] * v2[1] - v1[1] * v2[0]
    if abs(cross) < eps:
        # 平行情况：返回B点
        return B, B

    # 计算单位法向量（两种方向）
    n1 = (-v1[1], v1[0])
    n1_unit = (n1[0] / len1, n1[1] / len1)
    n2 = (v1[1], -v1[0])
    n2_unit = (n2[0] / len1, n2[1] / len1)

    n3 = (-v2[1], v2[0])
    n3_unit = (n3[0] / len2, n3[1] / len2)
    n4 = (v2[1], -v2[0])
    n4_unit = (n4[0] / len2, n4[1] / len2)

    # 构造偏移直线上的点
    P1 = (A[0] + R * n1_unit[0], A[1] + R * n1_unit[1])
    P2 = (A[0] + R * n2_unit[0], A[1] + R * n2_unit[1])
    P3 = (B[0] + R * n3_unit[0], B[1] + R * n3_unit[1])
    P4 = (B[0] + R * n4_unit[0], B[1] + R * n4_unit[1])

    # 求所有可能的交点
    O_candidates = []
    for p_start, v_dir in [(P1, v1), (P2, v1)]:
        for p2_start, v2_dir in [(P3, v2), (P4, v2)]:
            O = line_intersection(p_start, v_dir, p2_start, v2_dir, eps)
            if O is not None:
                O_candidates.append(O)

    # 检查每个交点对应的垂足
    for O in O_candidates:
        # 计算在AB上的垂足M
        vec_OA = (O[0] - A[0], O[1] - A[1])
        t = (v1[0] * vec_OA[0] + v1[1] * vec_OA[1]) / (len1 ** 2)
        if t < -eps or t > 1 + eps:
            continue
        M = (A[0] + t * v1[0], A[1] + t * v1[1])

        # 计算在BC上的垂足N
        vec_OB = (O[0] - B[0], O[1] - B[1])
        s = (v2[0] * vec_OB[0] + v2[1] * vec_OB[1]) / (len2 ** 2)
        if s < -eps or s > 1 + eps:
            continue
        N = (B[0] + s * v2[0], B[1] + s * v2[1])

        return M, N

    # 无解
    return None, None


# 测试示例
if __name__ == "__main__":
    A = (0, 0)
    B = (1, 0)
    C = (1, 1)
    R = 0.5
    M, N = find_MN(A, B, C, R)
    print("M:", M)  # 应输出 (0.5, 0.0)
    print("N:", N)  # 应输出 (1.0, 0.5)